import java.util.Scanner;

/**
 * 
 * 最左侧冗余覆盖子串
 * 
 * 题目描述

给定两个字符串 s1 和 s2 和正整数 k，其中 s1 长度为 n1，s2 长度为 n2。

在 s2 中选一个子串，若满足下面条件，则称 s2 以长度 k 冗余覆盖 s1

该子串长度为 n1 + k
该子串中包含 s1 中全部字母
该子串每个字母出现次数不小于 s1 中对应的字母
给定 s1，s2，k，求最左侧的 s2 以长度 k 冗余覆盖 s1 的子串的首个元素的下标，如果没有返回-1。

举例：

s1 = "ab"
s2 = "aabcd"
k = 1
则子串 “aab” 和 "abc" 均满足此条件，由于 "aab" 在 "abc" 的左侧，"aab" 的第一个元素下部为 0，因此输出 0

输入描述
输入三行，第一行为 s1，第二行为 s2，第三行为 k

s1 和 s2 只包含小写字母
输出描述
最左侧的 s2 以长度 k 冗余覆盖 s1 的子串首个元素下标，如果没有返回 -1。

备注
0 ≤ len(s1) ≤ 1000000
0 ≤ len(s2) ≤ 20000000
0 ≤ k ≤ 1000
用例
输入	ab
aabcd
1
输出	0
说明	子串aab和abc符合要求，由于aab在abc的左侧，因此输出aab的下标：0
输入	abc
dfs
10
输出	-1
说明	s2无法覆盖s1，输出 -1


 */
public class 最左侧冗余覆盖子串 {

    public static void main(String[] args) {
        
        try{

            Scanner scanner = new Scanner(System.in);

            //第一行  覆盖字符串
            String line1Str = scanner.nextLine();
            //第二行  被覆盖字符串
            String line2Str = scanner.nextLine();
            //第三行  k
            int K = Integer.parseInt(scanner.nextLine());


            int line1Len = line1Str.length();
            int line2Len = line2Str.length();

            //如果 line1Len+k 的长度大于line2Len，则不能覆盖

            if(line1Len + K > line2Len){

                System.out.println("-1");
            }  else {

                //采用int[128]数组来表示小写字母出现次数数组
                //由于字符串s1中都是小写字母，因此每个字母的ASCII码范围是97~122，因此这里初始化128长度数组来作为统计容器
                int[] charCount = new int[128];

                //计算line1Str中字母出现的次数

                for(char c : line1Str.toCharArray()){

                    charCount[c]++;
                }

                int total = line1Len;

                //滑动窗口  长度 也就是截取覆盖的字符串长度
                int resultStrLen = line1Len+K;

                // // 统计s2的0~len范围内出现的s1中字符的次数
                for(int j=0; j<resultStrLen; j++){

                    char c = line2Str.charAt(j);

                    // 如果s2的0~len范围内的字符c，在count[c]存在，则说明c是s1内有的字符，
                    // 此时我们需要count[c]--，如果自减之前，count[c] > 0，则自减时，total也应该--,否则total不--
                    if (charCount[c]-- > 0) {
                        total--;
                    }
 
                    // 如果total为0了，则说明在s2的0~len范围内找到了所有s1中字符
                    if (total == 0) {
                        // 此时可以直接返回起始索引0

                        System.out.println(""+0);
                        return;
                    }
                }

                // 下面是从左边界1开始的滑动窗口，利用差异思想，避免重复部分求解
                for (int i = 1; i <= line2Len - resultStrLen; i++) {
                    // 滑动窗口右移一格后，失去了s2[i - 1]，得到了s2[i - 1 + len]，其余部分不变
                    char left = line2Str.charAt(i - 1);
                    char right = line2Str.charAt(i - 1 + resultStrLen);
         
                    if (charCount[left]++ >= 0) {
                        total++;
                    }
         
                    if (charCount[right]-- > 0) {
                        total--;
                    }
         
                    if (total == 0) {
                        System.out.println(""+i);
                    }
                }
                System.out.println("-1");



            }


        }catch(Exception e){
            e.printStackTrace();
        }
    }
}